#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long long
#define Add(a,b) (((a) + (b)) % mod)
#define Sub(a,b) (((a) - (b) + mod) % mod)
#define Mul(a,b) ((a) * (b) % mod)
#define chAdd(a,b) (a = Add(a,b))
#define chMul(a,b) (a = Mul(a,b))

using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 10;
const int mod = 6661;
int n,q,m;
vector<vector<int>> c;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int qmi(int a,int b){
    int res = 1;
    while (b){
        if (b & 1) chMul(res,a);
        chMul(a,a); b >>= 1;
    } return res;
}

inline void init(int n){
    c.resize(n + 1);
    for (re int i = 0;i <= n;i++){
        c[i].resize(i + 1);
        c[i][0] = c[i][i] = 1;
        for (re int j = 1;j < i;j++) c[i][j] = Add(c[i - 1][j - 1],c[i - 1][j]);
    }
    for (re int i = 0;i <= n;i++){
        for (re int j = 1;j <= i;j++) chAdd(c[i][j],c[i][j - 1]);
    }
}

inline int get(int x,int l,int r){
    if (l > x && r > x) return 0;
    else if (l <= x && r > x) return Sub(c[x][x],c[x][l - 1]);
    else return Sub(c[x][r],c[x][l - 1]);
}

struct{
    #define ls(u) (u << 1)
    #define rs(u) (u << 1 | 1)
    #define mid (tr[u].l + tr[u].r >> 1)
    
    struct node{
        int l,r;
        int sum;
        pii tag;
    }tr[N << 2];
    
    inline void pushup(int u){ tr[u].sum = Add(tr[ls(u)].sum,tr[rs(u)].sum); }

    inline void calc(int u,pii k){
        tr[u].tag = k;
        tr[u].sum = get(k.fst,tr[u].l - k.snd + 1,tr[u].r - k.snd + 1);
    }

    inline void pushdown(int u){
        if (tr[u].tag.snd) calc(ls(u),tr[u].tag),calc(rs(u),tr[u].tag);
        tr[u].tag = {0,0};
    }

    inline void build(int u,int l,int r){
        tr[u] = {l,r};
        // if (l == r) cerr << l << " " << c[m][l] << " ???\n";
        if (l == r) return (tr[u].sum = get(m,l,l)),void();
        build(ls(u),l,mid); build(rs(u),mid + 1,r);
        pushup(u);
    }

    inline void modify(int u,int l,int r,pii k){
        if (l <= tr[u].l && tr[u].r <= r) return calc(u,k);
        pushdown(u);
        if (l <= mid) modify(ls(u),l,r,k);
        if (r > mid) modify(rs(u),l,r,k);
        pushup(u);
    }

    inline int query(int u,int l,int r){
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
        pushdown(u);
        if (l <= mid && r > mid) return Add(query(ls(u),l,r),query(rs(u),l,r));
        else if (l <= mid) return query(ls(u),l,r);
        else return query(rs(u),l,r);
    }

    #undef ls
    #undef rs
    #undef mid
}T;

signed main(){
    freopen("izumi.in","r",stdin);
    freopen("izumi.out","w",stdout);
    n = read(),q = read(),m = read() % mod;
    init(6660); T.build(1,1,n);
    // cerr << "=====\n"; return 0;
    while (q--){
        int op = read();
        if (op == 1){
            int l,r,x;
            l = read(),r = read(),x = read() % mod;
            T.modify(1,l,r,{x,l});
        }
        else{
            int l,r; l = read(),r = read();
            printf("%lld\n",T.query(1,l,r));
        }
    }
    return 0;
}